package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/backspace-string-compare/'>比较含退格的字符串(Backspace String Compare)</a>
 * <p>给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。</p>
 * <p>注意：如果对空文本输入退格字符，文本继续为空。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：s = "ab#c", t = "ad#c"
 *      输出：true
 *      解释：s 和 t 都会变成 "ac"。
 *
 *  示例 2：
 *      输入：s = "ab##", t = "c#d#"
 *      输出：true
 *      解释：s 和 t 都会变成 ""。
 *
 *  示例 3：
 *      输入：s = "a#c", t = "b"
 *      输出：false
 *      解释：s 会变成 "c"，但 t 仍然是 "b"。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= s.length, t.length <= 200</li>
 *     <li>s 和 t 只含有小写字母以及字符 '#'</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/18 17:04
 */
public class LC0844BackspaceStringCompare_S {
    static class Solution {
        /**
         * 双指针。节约空间
         * <p>由于#号只会消除左边的一个字符，所以对右边的字符无影响，所以我们选择从后往前遍历字符串。查找经退格处理后的有效字符串，进行对比</p>
         */
        public boolean backspaceCompare(String s, String t) {
            int sIdx = s.length() - 1;
            int tIdx = t.length() - 1;

            int sSkipCnt = 0;
            int tSkipCnt = 0;
            while (sIdx >= 0 || tIdx >= 0) {
                // 找到s字符串中第一个有效字符
                while (sIdx >= 0) {
                    if (s.charAt(sIdx) == '#') {
                        ++sSkipCnt;
                        --sIdx;
                    } else if (sSkipCnt > 0) {
                        --sSkipCnt;
                        --sIdx;
                    } else {
                        break;
                    }
                }
                // 找到t字符串中第一个有效字符
                while (tIdx >= 0) {
                    if (t.charAt(tIdx) == '#') {
                        ++tSkipCnt;
                        --tIdx;
                    } else if (tSkipCnt > 0) {
                        --tSkipCnt;
                        --tIdx;
                    } else {
                        break;
                    }
                }

                if (sIdx >= 0 && tIdx >= 0) {
                    // 如果字符不相等，则返回false
                    if (s.charAt(sIdx) != t.charAt(tIdx)) {
                        return false;
                    }
                } else {
                    // 都处理完成，返回true；否则返回false
                    return sIdx < 0 && tIdx < 0;
                }
                // 继续向前查询下一个有效字符
                --sIdx;
                --tIdx;
            }
            return true;
        }

        /**
         * 栈。代码简单
         */
        public boolean backspaceCompare2(String s, String t) {
            return rebuildStr(s).equals(rebuildStr(t));
        }

        private String rebuildStr(String str) {
            int idx = 0;
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '#') {
                    if (idx > 0) {
                        --idx;
                    }
                } else {
                    chars[idx] = chars[i];
                    ++idx;
                }
            }
            return new String(chars, 0, idx);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.backspaceCompare("ab#c", "ad#c"));  // true
        System.out.println(solution.backspaceCompare("ab##", "c#d#"));  // true
        System.out.println(solution.backspaceCompare("a#c", "b"));      // false
        System.out.println(solution.backspaceCompare("a##c", "#a#c"));  // true
    }
}
